#

"""
NC61 两数之和
https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f?tpId=117&&tqId=37756&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

输入：[3,2,4],6
返回值：[2,3]
说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]       
"""

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @param target int整型
# @return int整型一维数组
#

from typing import List


class Solution:
    def method1(self, nums: List[int], target: int) -> List[int]:
        """
        暴力解法，无法通过测试
        O(n^2)
        """
        size = len(nums)
        for i in range(size-1):  # 每个数字只可以使用1次
            for j in range(i+1, size):
                if nums[i] + nums[j] == target:
                    return [i+1, j+1]  # 索引默认从1开始

        # 没找到答案
        return []

    def method2(self, nums: List[int], target: int) -> int:
        """
        以空间换时间，把要找的数的索引存起来
        """
        memo = {}

        for i, v in enumerate(nums):
            tmp = target - v  # 和当前v配对的tmp值是否出现过
            if tmp in memo:
                return [memo[tmp]+1, i+1]
            else:
                memo[v] = i

        return []

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # write code here
        size = len(numbers)
        assert size >= 2, "传入的参数至少应该有2个数字"
        # 没说一定有结果，没有结果的时候，先默认返回[]
        # 也没说可能有多组解怎么办，先按照只要有解就退出处理
        return self.method2(numbers, target)


def test():
    obj = Solution()
    nums = [3, 2, 4]
    target = 6
    res = obj.twoSum(nums, target)
    print(res)


if __name__ == "__main__":
    test()
